/**
 * 给你一个整数数组 nums ，按要求返回一个新数组counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于nums[i] 的元素的数量。
 *
 * 链接：https://leetcode.cn/problems/count-of-smaller-numbers-after-self
 * 题解：https://leetcode.cn/problems/count-of-smaller-numbers-after-self/
 * https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/jian-zhi-offer-51-shu-zu-zhong-de-ni-xu-pvn2h/
 */
class CountSmaller {
   Pair[] tmp;
   int[] count;
    public List<Integer> countSmaller(int[] nums) {
       List<Integer> ret=new ArrayList<>();
        int len=nums.length;
        tmp=new Pair[len];
        Pair[] arr=new Pair[len];
        for(int i=0;i<len;i++) {
            arr[i]=new Pair(nums[i],i);
        }
        count=new int[len];
        mergeSort(arr,0,len-1);
        for(int num:count) {
            ret.add(num);
        }
        return ret;
    }
    public void mergeSort(Pair[] arr,int left,int right) {
        if(left>=right) {
            return;
        }
        int mid=left+((right-left)>>>1);
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1,right);
        merge(arr,left,mid,right);
    }
    public void merge(Pair[] arr,int left,int mid,int right) {
        int s1=left,b1=mid;
        int s2=mid+1,b2=right;
        int i=0;
        while(s1<=mid&&s2<=right) {
            if(arr[s1].val<=arr[s2].val) {
                count[arr[s1].id]+=s2-mid-1;
                tmp[i++]=arr[s1++];
            } else {
             
               tmp[i++]=arr[s2++];
            }
        }
        while(s1<=mid) {
            count[arr[s1].id]+=s2-mid-1;
            tmp[i++]=arr[s1++];
        } 
        while(s2<=right) {
            tmp[i++]=arr[s2++];
        }
        i=0;
        for(int k=left;k<=right;k++) {
            arr[k]=tmp[i++];
        }
    }
}
class Pair {
    public int val;
    public int id;
    public Pair(int val,int id) {
        this.val=val;
        this.id=id;
    }
}